import java.util.Stack;

/**
 * 155. 最小栈（与 剑指 Offer 30 同）
 * https://leetcode-cn.com/problems/min-stack/
 */
public class Solutions_155 {
    public static void main(String[] args) {
        MinStack obj = new MinStack();
        obj.push(-2);
        obj.push(0);
        obj.push(-3);
        int res1 = obj.getMin();  // output: -3
        System.out.println(res1);
        obj.pop();
        int res2 = obj.top();  // output: 0
        System.out.println(res2);
        int res3 = obj.getMin();  // output: -2
        System.out.println(res3);
    }
}

class MinStack {
    private Stack<Integer> stack = null;  // 存储元素的栈
    private Stack<Integer> minStack = null;  // 辅助栈：记录与 stack 中每个元素所对应的最小值

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
        // 给定默认值
        minStack.push(Integer.MAX_VALUE);
    }
    // 将元素 x 入栈
    public void push(int x) {
        stack.push(x);
        // x 与 x 对应的最小值，即栈中的最小元素（对应的最小值只能是先入栈的元素，而不是后入栈）
        minStack.push(Math.min(x, minStack.peek()));
    }
    // 栈顶元素出栈
    public void pop() {
        stack.pop();
        // 同时与其对应的最小值也弹出
        minStack.pop();
    }
    // 获取栈顶元素
    public int top() {
        return stack.peek();
    }
    // 检索栈中的最小元素
    public int getMin() {
        return minStack.peek();
    }
}
